1. Technical Field
The present invention relates to a method and system for reducing the storage occupation of a color bitmap, particularly for use in those systems where a bitmap must be stored or transmitted through a network.
2. Description of Related Art
Bitmap size is a critical parameter, particularly when the bitmap is to be stored or transmitted over a network. The storage occupation in the first case and the speed of transmission in the latter can be heavily affected. For this reason many techniques have been developed for reducing the size of bitmaps and consequently their storage occupation and speed of transmission. One kind of application, even if not the only one, where this need is extremely important is “remote control”. Remote control programs are a special category of communication applications; they go beyond just connecting a computer with another computer to actually taking control of it. By connecting through phone lines and modems or through LAN connections, these programs can put all the resources of one data processing system (e.g. a personal computer or a workstation), usually called the target, under the complete control of another data processing system (e.g. a personal computer or a workstation, connected with a LAN), usually called the controller. The controller screen duplicates the target one. The keyboard of the controller can enter characters directly on the target data processing system; the mouse of the controller can move the mouse pointer on the target screen. The controller screen constantly receives data from the target data processing system screen. Likewise, the keyboard of the controller sends data to the target data processing system every time a key is hit. For all practical purposes, the controller user may as well be sitting in front of the target data processing system.
This kind of remote control software can be useful in a number of circumstances. Just as an example an office personal computer system can be controlled and operated from home personal computers. If the office PC is left connected (e.g. to a modem), the control can be taken from the home PC and all the resources of the target PC can be controlled and used remotely. A more specific use is to dial in (e.g. via modem) to a network—connected PC at the office, log in, and run network applications or update shared files on the network.
The bottleneck caused by transmission lines can have a significant effect on the speed of remote control operations. To boost performances, remote control programs try to reduce and minimize the amount of data that needs to be transmitted over the communication lines (e.g. LAN or telephone cables). The refresh of the video image on the display screen of the target PC, which should be duplicated on the controller PC, constitutes the main factor in the transmission speed, due to the large quantity of information which has to be transferred. In the past, remote control programs worked by sending and refreshing the entire image of the target PC screen to the remote PC every fraction of a second. The constant rate at which the screen images were sent to the controller PC was called the screen refresh rate. The controller PC screen accurately reflected the target PC screen as changes at the target PC would be included in the next screen refresh. This approach was, of course, not very satisfactory in terms of speed, because of the enormous amount of data to be transmitted at each refresh.
Often, a change of the image is limited to a small section of the screen (e.g. pulling down a menu, highlighting an object) and only the changed data need to be refreshed. The controller system can use the screen data previously received and just refresh the modified part of the screen. By cutting out redundant screen refresh data, a remote control program can improve the response time. Cache memories speed the performance of hard drives and memory chips, and can also be useful for remote control programs. The idea behind a cache is to keep recently used data in a temporary storage area that is quickly accessible. If the data are soon needed again, it is much quicker to access them from a fast-access temporary storage area than to retrieve from the original source. According to this technique, elements of a recently displayed screen are saved as a cache in extended memory. The entire age redraws from the controller PC screen cache, eliminating the need to transfer large amounts of information over the modem from the target to the controller PC. Screen elements that are often redrawn from a screen cache include bitmaps, text and fonts.
In the transmission of a bitmap image, one of the heaviest information to send is the color of each pixel. In the well known RGB format, the color of each pixel is represented by three octets (i.e. three bytes having 8 bits each), one for the Red, one for the Green and one for the Blue. The maximum possible number of differnt colors is 16,777,216, i.e. 2**24. This representation with all the possible colors is called “true color”.
In remote control systems (as in many other circumstances) this detailed color representation is not always needed and the transmission of all this information frequently constitutes an unwanted burden. Usually for the scope of the controller system, a poorer color image would be enough. For this reason, many remote control systems use color reduction algorithms to reduce the color representation from 24 (or 16) bits to 8 bits or even 4 bits. An example of a function implementing these algorithms is GetDIBits from Microsoft. A drawback of prior art color reduction functions is that they require a relatively long computation time to perform this color reduction, mostly due to the effort of creating a reduced image as close as possible to the original one. In remote control system, where these operations must be performed very often at a very high speed rate, the color reduction delay is unacceptable. An alternative reduction mechanism is the one implemented by Tivoli Remote Control by International Business Machines Corp and described in GB Patent Application 9917455.9. This mechanism has the advantage of a faster processing, balanced by a reduced precision in the correspondance between the resulting “reduced” colors and the original ones. This reduced precision is normally acceptable, particularly in remote control systems, and preferrable to a delay in computation. A method combining the speed and easiness of processing with the precision of the results would therefore be highly welcome.